package com.zjsru.oneDay202209;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/9/17
 * 两个相同字符之间的最长子字符串
 *
 * 输入：s = "aa"
 * 输出：0
 * 解释：最优的子字符串是两个 'a' 之间的空子字符串。
 *
 * 输入：s = "abca"
 * 输出：2
 * 解释：最优的子字符串是 "bc" 。
 *
 * 输入：s = "cbzxy"
 * 输出：-1
 * 解释：s 中不存在出现出现两次的字符，所以返回 -1 。
 */
public class MaxLengthBetweenEqualCharacters {
    /**
     * 双指针，需要两个循环
     * */
    public int maxLengthBetweenEqualCharacters(String s) {
        int ans = -1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    ans = Math.max(ans, j - i - 1);
                }
            }
        }
        return ans;
    }
    
    /**
     * 记录下每个字符最开始出现的下标即可
     * 用数组形式循环一次实现
     * */
    public int maxLengthBetweenEqualCharacters2(String s) {
        int[] nums = new int[26];
        int len = s.length(), ans = -1;
        Arrays.fill(nums, 310);
        for (int i = 0; i < len; i++) {
            int u = s.charAt(i) - 'a';
            //将获取的u 作为存入数组的下标，和i比较即是判断距离
            nums[u] = Math.min(nums[u], i);
            //i - nums[u]即是当前位数和上一位重复的字母之间的距离. -1代表计数获取的是中间位数
            ans = Math.max(ans, i - nums[u] - 1);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        MaxLengthBetweenEqualCharacters maxLengthBetweenEqualCharacters = new MaxLengthBetweenEqualCharacters();
        String s = "caaa";
        System.out.println(maxLengthBetweenEqualCharacters.maxLengthBetweenEqualCharacters2(s));
    }
}
